package com.LeeCode;

/**
 * 字符相同的最短子字符串 II
 */

public class Code3399 {
    public static void main(String[] args) {
        String s = "0110";
        int numOps = 1;
        System.out.println(new Code3399().minLength(s, numOps));
    }

    public int minLength(String s, int numOps) {
        int left = 0, right = s.length();
        char[] chars = s.toCharArray();
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(chars, mid, numOps))
                right = mid;
            else
                left = mid;
        }
        return right;
    }

    private boolean check(char[] s, int m, int numOps) {
        int n = s.length;
        int cnt = 0;
        if (m == 1) {
            // 改成 0101...
            for (int i = 0; i < n; i++) {
                // 如果 s[i] 和 i 的奇偶性不同，cnt 加一
                cnt += (s[i] ^ i) & 1;
            }
            // n-cnt 表示改成 1010...
            cnt = Math.min(cnt, n - cnt);
        } else {
            int k = 0;
            for (int i = 0; i < n; i++) {
                k++;
                // 到达连续相同子串的末尾
                if (i == n - 1 || s[i] != s[i + 1]) {
                    cnt += k / (m + 1);
                    k = 0;
                }
            }
        }
        return cnt <= numOps;
    }
}

